package LK_DP;

import java.util.HashMap;

public class Test {
    /*专门刷力扣的动态规划*/
    //70
    // 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
    //每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
    public int climbStairs(int n) {
        //动态规划 1:划分子问题 2:找出递推关系 3:计算顺序 4:优化
        int[] dp=new int[n];
        if(n < 2){
            return n;
        }

        dp[0]=1;
        dp[1]=2;
        for(int i=2; i < n ; i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n-1];

    }
    /*斐波那契数*/
    public int fib(int n) {
        if(n < 2){
            return n;
        }
        int[] dp=new int[n+1];
        dp[0]=0;
        dp[1]=1;
        for(int i =2; i <= n ; i++ ){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }


    public int deleteAndEarn(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        } else if (nums.length == 1) {
            return nums[0];
        }
        int len = nums.length;
        int max = nums[0];
        for (int i = 0; i < len; ++i) {
            max = Math.max(max, nums[i]);
        }
//      构造一个新的数组all
        int[] all = new int[max + 1];
        for (int item : nums) {
            all[item] ++;
        }

        int[] dp = new int[max + 1];
        dp[1] = all[1] * 1;
        dp[2] = Math.max(dp[1], all[2] * 2);
//      动态规划求解
        for (int i = 2; i <= max; ++i) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + i * all[i]);
        }
        return dp[max];
    }

    public static void main(String[] args) {
        int[][] arr={{1,2}, {5,6},{1,1}};
        Test test=new Test();
        int ret=test.minPathSum(arr);
        System.out.println(ret);
    }
    public int minPathSum(int[][] grid) {
        //一条路径从上往下走,一条路径从下走
       int sum=0;
        int m= grid.length;
        int n=grid[0].length;
        int i = m-1;
        int j=n-1;
        while (j-1 >=0 || i-1>=0){
            if (j-1 >=0 && i-1 >= 0){
                int k=grid[i][j-1];
                int k1=grid[i-1][j];
                if (k > k1){
                    i--;
                    sum+=k1;
                }else {
                    j--;
                    sum+=k;
                }
            }else if (j-1 >= 0){
                sum+=grid[i][j-1];
                j--;
            }else {
                sum+=grid[i-1][j];
                i--;
            }
        }
        return sum+grid[m-1][n-1];
    }



}
